/**
 * @file ThreadBinaryTreePrac.c
 * @desc ${DESC} 
 * @author WangBlue(wangjiping596@gmail.com)
 * @date: 2025/10/14 17:36
 * @version: 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


typedef struct BinNode {
    char data;
    struct BinNode *lChild;
    struct BinNode *rChild;
    int ltag, rtag;
}BinNode;


BinNode* createBinNode(char data) {
    BinNode* newNode = (BinNode*) malloc(sizeof(BinNode));
    if (newNode == NULL) {
        return NULL;
    }
    newNode->data = data;
    newNode->lChild = NULL;
    newNode->rChild = NULL;
    newNode->ltag = 0;
    newNode->rtag = 0;
    return newNode;
}

BinNode* createSimpleTree() {
    BinNode* A = createBinNode('A');
    BinNode* B = createBinNode('B');
    BinNode* C = createBinNode('C');
    BinNode* D = createBinNode('D');
    BinNode* E = createBinNode('E');
    A->lChild = B;
    A->rChild = C;
    B->lChild = D;
    B->rChild = E;
    return A;
}

void inOrder(BinNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->lChild);
    printf("%c ", root->data);
    inOrder(root->rChild);
}


void threadInOrder(BinNode* root, BinNode** pre) {
    if (root == NULL) {
        return;
    }
    threadInOrder(root->lChild, pre);
    // 前驱
    if (!root->lChild) {
        root->ltag = 1;
        root->lChild = *pre;
    }

    // 后继
    if ((*pre) && !(*pre)->rChild) {
        (*pre)->rtag = 1;
        (*pre)->rChild = root;
    }
    *pre = root;
    threadInOrder(root->rChild, pre);

}

void inOrderTraverseRecursive(BinNode* root) {
    if (root == NULL) {
        return;
    }
    if (root->ltag == 0) {
        inOrderTraverseRecursive(root->lChild);
    }
    printf("%c ", root->data);
    if (root->rtag == 0) {
        inOrderTraverseRecursive(root->rChild);
    }

}

BinNode* firstNode(BinNode* root) {
    if (root == NULL) {
        return NULL;
    }
    while (root->ltag == 0) {
        root = root->lChild;
    }
    return root;
}


BinNode* preNode(BinNode* root) {
    if (root == NULL) {
        return NULL;
    }
    if (root->ltag == 1) {
        return root->lChild;
    }
    return firstNode(root->lChild);
}

BinNode* nextNode(BinNode* root) {
    if (root == NULL) {
        return NULL;
    }
    if (root->rtag == 1) {
        return root->rChild;
    } else {
        BinNode *p = root->rChild;
        if (!p) return NULL;
        while (p->rtag == 0 && p->rChild) {
            p = p->rChild;
        }
        return p;
    }
}

BinNode* findNode(BinNode* root, char target) {
    if (root == NULL) {
        return NULL;
    }
    for (BinNode* p = firstNode(root); p !=NULL; p = nextNode(p)) {
        if (p->data == target) {
            return p;
        }
    }
}

void inOrderTraverseThreaded(BinNode* root) {
    if (root == NULL) {
        return;
    }
    for (BinNode *p = firstNode(root); p != NULL; p = nextNode(p)) {
        printf("%c ", p->data);
    }
    printf("\n");
}

int main() {
    BinNode* root = createSimpleTree();
    inOrder(root);

    BinNode *pre = NULL;
    threadInOrder(root, &pre);
    printf("\n");

    // 查找并输出前驱/后继
    char target = 'E';
    BinNode* nodeE = findNode(root, target);
    if (nodeE) {
        printf("node %c find!\n", target);
        BinNode* pred = preNode(nodeE);
        BinNode* succ = nextNode(nodeE);

        if (pred) printf("preNode: %c\n", pred->data);
        else printf("preNode: NULL\n");

        if (succ) printf("nextNode: %c\n", succ->data);
        else printf("nextNode: NULL\n");
    } else {
        printf("node %c NotFind!\n", target);
    }
    printf("----------------------------------------");
    return 0;
}
